unit heContnrs_List_test;

{$mode objfpc}{$H+}

interface

uses
  fpcunit,
  heContnrs,
  heContnrs_test;

type

  { TheListTest }

  generic TheListTest<TList_, TItem, TNode> = class(TTestCase)
  public type
    TNodeP = ^TNode;
  private
    List: TList_;
  protected
    function Item(const N: Integer): TItem; virtual; // abstract;
    function Value(const It: TItem): Integer; virtual; // abstract;
    procedure CheckLinks;
    procedure Done(Node: TNodeP); virtual;
    procedure SetUp; override;
    procedure TearDown; override;
  published
    procedure TestCreate;
    procedure TestPushFront;
    procedure TestPushBack;
    procedure TestClear;
    procedure TestMoveToFront;
    procedure TestMoveToBack;
    procedure TestInsertAfter;
    procedure TestInsertBefore;
    procedure TestMoveAfter;
    procedure TestMoveBefore;
    procedure TestExtract;
    procedure TestRemove;
  end;

  _TTestListInt = specialize TheList<Integer>;
  TTestListInt = class(_TTestListInt);
  _TTestListStr = specialize TheList<String>;
  TTestListStr = class(_TTestListStr);
  _TTestListInterface = specialize TheList<IInterface>;
  TTestListInterface = class(_TTestListInterface);
  _TTestListObject = specialize TheObjectList<TTracedObject>;
  TTestListObject = class(_TTestListObject);

  { TheIntListTest }

  _TheIntListTest = specialize TheListTest<TTestListInt, Integer, TTestListInt.TNode>;
  TheIntListTest = class(_TheIntListTest)
  protected
    function Item(const N: Integer): Integer; override;
    function Value(const It: Integer): Integer; override;
  published
    procedure TestGetEnumerator;
    procedure TestReversed;
  end;

  { TheStrListTest }

  _TheStrListTest = specialize TheListTest<TTestListStr, String, TTestListStr.TNode>;
  TheStrListTest = class(_TheStrListTest)
  protected
    function Item(const N: Integer): String; override;
    function Value(const It: String): Integer; override;
  published
    procedure TestGetEnumerator;
    procedure TestReversed;
  end;

  { TheInterfaceListTest }

  _TheInterfaceListTest = specialize TheListTest<TTestListInterface, IInterface, TTestListInterface.TNode>;
  TheInterfaceListTest = class(_TheInterfaceListTest)
  protected
    function Item(const N: Integer): IInterface; override;
    function Value(const It: IInterface): Integer; override;
  published
    procedure TestGetEnumerator;
    procedure TestReversed;
  end;

  { TheObjectListTest }

  _TheObjectListTest = specialize TheListTest<TTestListObject, TTracedObject, TTestListObject.TNode>;
  TheObjectListTest = class(_TheObjectListTest)
  private type
    TNodeP_ = TTestListObject.PNode;
  protected
    function Item(const N: Integer): TTracedObject; override;
    function Value(const It: TTracedObject): Integer; override;
    procedure Done(Node: TNodeP_); override;
    procedure SetUp; override;
  published
    procedure TestCreate2;
    procedure TestCreate3;
    procedure TestGetEnumerator;
    procedure TestReversed;
  end;

implementation

uses
  Classes,
  SysUtils,
  testregistry;

{ TheIntListTest }

function TheIntListTest.Item(const N: Integer): Integer;
begin
  Result := N;
end;

function TheIntListTest.Value(const It: Integer): Integer;
begin
  Result := It;
end;

procedure TheIntListTest.TestGetEnumerator;
const N = 10;
var
  I, J: Integer;
  V: TItem;
  A: array[0..N - 1] of TItem;
begin
  J := 0;
  for V in List do
    Inc(J);
  AssertEquals(0, J);
  for I := 0 to N - 1 do begin
    A[I] := Item(I);
    List.PushBack(A[I]);
    J := 0;
    for V in List do begin
      AssertEquals('V', Value(A[J]), Value(V));
      Inc(J);
    end;
    AssertEquals(I + 1, J);
  end;
end;

procedure TheIntListTest.TestReversed;
const N = 10;
var
  I, J: Integer;
  V: TItem;
  A: array[0..N - 1] of TItem;
begin
  J := 0;
  for V in List do
    Inc(J);
  AssertEquals(0, J);
  for I := 0 to N - 1 do begin
    A[I] := Item(I);
    List.PushFront(A[I]);
    J := 0;
    for V in List.Reversed do begin
      AssertEquals('V', Value(A[J]), Value(V));
      Inc(J);
    end;
    AssertEquals(I + 1, J);
  end;
end;

{ TheStrListTest }

function TheStrListTest.Item(const N: Integer): String;
begin
  Result := IntToStr(N);
end;

function TheStrListTest.Value(const It: String): Integer;
begin
  Result := StrToInt(It);
end;

procedure TheStrListTest.TestGetEnumerator;
const N = 10;
var
  I, J: Integer;
  V: TItem;
  A: array[0..N - 1] of TItem;
begin
  J := 0;
  for V in List do
    Inc(J);
  AssertEquals(0, J);
  for I := 0 to N - 1 do begin
    A[I] := Item(I);
    List.PushBack(A[I]);
    J := 0;
    for V in List do begin
      AssertEquals('V', Value(A[J]), Value(V));
      Inc(J);
    end;
    AssertEquals(I + 1, J);
  end;
end;

procedure TheStrListTest.TestReversed;
const N = 10;
var
  I, J: Integer;
  V: TItem;
  A: array[0..N - 1] of TItem;
begin
  J := 0;
  for V in List do
    Inc(J);
  AssertEquals(0, J);
  for I := 0 to N - 1 do begin
    A[I] := Item(I);
    List.PushFront(A[I]);
    J := 0;
    for V in List.Reversed do begin
      AssertEquals('V', Value(A[J]), Value(V));
      Inc(J);
    end;
    AssertEquals(I + 1, J);
  end;
end;

{ TheInterfaceListTest }

function TheInterfaceListTest.Item(const N: Integer): IInterface;
begin
  Result := TInterfacedTracedObject.Create(nil, N);
end;

function TheInterfaceListTest.Value(const It: IInterface): Integer;
begin
  Result := (It as TInterfacedTracedObject).ID;
end;

procedure TheInterfaceListTest.TestGetEnumerator;
const N = 10;
var
  I, J: Integer;
  V: TItem;
  A: array[0..N - 1] of TItem;
begin
  J := 0;
  for V in List do
    Inc(J);
  AssertEquals(0, J);
  for I := 0 to N - 1 do begin
    A[I] := Item(I);
    List.PushBack(A[I]);
    J := 0;
    for V in List do begin
      AssertEquals('V', Value(A[J]), Value(V));
      Inc(J);
    end;
    AssertEquals(I + 1, J);
  end;
end;

procedure TheInterfaceListTest.TestReversed;
const N = 10;
var
  I, J: Integer;
  V: TItem;
  A: array[0..N - 1] of TItem;
begin
  J := 0;
  for V in List do
    Inc(J);
  AssertEquals(0, J);
  for I := 0 to N - 1 do begin
    A[I] := Item(I);
    List.PushFront(A[I]);
    J := 0;
    for V in List.Reversed do begin
      AssertEquals('V', Value(A[J]), Value(V));
      Inc(J);
    end;
    AssertEquals(I + 1, J);
  end;
end;

{ TheObjectListTest }

function TheObjectListTest.Item(const N: Integer): TTracedObject;
begin
  Result := TTracedObject.Create(nil, N);
end;

function TheObjectListTest.Value(const It: TTracedObject): Integer;
begin
  Result := It.ID;
end;

procedure TheObjectListTest.Done(Node: TNodeP_);
begin
  Node^.Item.Free;
  inherited Done(Node);
end;

procedure TheObjectListTest.SetUp;
begin
  List := TTestListObject.Create(True);
end;

procedure TheObjectListTest.TestGetEnumerator;
const N = 10;
var
  I, J: Integer;
  V: TItem;
  A: array[0..N - 1] of TItem;
begin
  J := 0;
  for V in List do
    Inc(J);
  AssertEquals(0, J);
  for I := 0 to N - 1 do begin
    A[I] := Item(I);
    List.PushBack(A[I]);
    J := 0;
    for V in List do begin
      AssertEquals('V', Value(A[J]), Value(V));
      Inc(J);
    end;
    AssertEquals(I + 1, J);
  end;
end;

procedure TheObjectListTest.TestReversed;
const N = 10;
var
  I, J: Integer;
  V: TItem;
  A: array[0..N - 1] of TItem;
begin
  J := 0;
  for V in List do
    Inc(J);
  AssertEquals(0, J);
  for I := 0 to N - 1 do begin
    A[I] := Item(I);
    List.PushFront(A[I]);
    J := 0;
    for V in List.Reversed do begin
      AssertEquals('V', Value(A[J]), Value(V));
      Inc(J);
    end;
    AssertEquals(I + 1, J);
  end;
end;

procedure TheObjectListTest.TestCreate2;
var
  Tracer: TBits;
  L: TTestListObject;
begin
  L := TTestListObject.Create(True);
  try
    AssertTrue(L.OwnObjects);
    Tracer := TBits.Create;
    try
      L.PushBack(TTracedObject.Create(Tracer, 1));
      L.Clear;
      AssertFalse('Item dead', Tracer[1]);
    finally
      Tracer.Free;
    end;
  finally
    L.Free;
  end;
end;

procedure TheObjectListTest.TestCreate3;
var
  Tracer: TBits;
  L: TTestListObject;
  Obj: TTracedObject;
begin
  L := TTestListObject.Create(False);
  try
    AssertFalse(L.OwnObjects);
    Tracer := TBits.Create;
    try
      Obj := TTracedObject.Create(Tracer, 1);
      try
        L.PushBack(Obj);
        L.Clear;
        AssertTrue('Item alive', Tracer[1]);
      finally
        Obj.Free;
      end;
    finally
      Tracer.Free;
    end;
  finally
    L.Free;
  end;
end;

{ TheListTest }

function TheListTest.Item(const N: Integer): TItem;
begin
  Assert(N = N); // hint off
  Initialize(Result); // hint off
  raise EAbstractError.Create(Format('%s.Item', [ClassName]));
end;

function TheListTest.Value(const It: TItem): Integer;
begin
  Assert(@It = @It); // hint off
  Initialize(Result); // hint off
  raise EAbstractError.Create(Format('%s.Value', [ClassName]));
end;

procedure TheListTest.CheckLinks;
var
  Node1, Node2: TNodeP;
  I: Integer;
begin
  if List.Count = 0 then begin
    if List.First <> nil then
      raise Exception.Create('CheckLinks: .Count = 0 and .First <> nil');
    if List.Last <> nil then
      raise Exception.Create('CheckLinks: .Count = 0 and .Last <> nil');
    Exit;
  end;

  if List.First = nil then
    raise Exception.Create('CheckLinks: .Count <> 0 and .First = nil');
  if List.Last = nil then
    raise Exception.Create('CheckLinks: .Count <> 0 and .Last = nil');
  if List.Count = 1 then begin
    if List.First <> List.Last then
      raise Exception.Create('CheckLinks: .Count = 1 and .First <> .Last');
    if List.First^.Next <> nil then
      raise Exception.Create('CheckLinks: .Count = 1 and .First^.Next <> nil');
    if List.First^.Prev <> nil then
      raise Exception.Create('CheckLinks: .Count = 1 and .First^.Prev <> nil');
    Exit;
  end;

  Node1 := nil;
  Node2 := List.First;
  I := 0;
  while Node2 <> nil do begin
    if Node2^.Prev <> Node1 then
      raise Exception.Create(Format('CheckLinks: Node[%d]^.Prev <> prev node', [I]));
    Node1 := Node2;
    Node2 := Node2^.Next;
    Inc(I);
  end;
  if I <> List.Count then
    raise Exception.Create(Format('CheckLinks: a) .Count = %d but %d node(s)', [List.Count, I]));
  Node1 := nil;
  Node2 := List.Last;
  I := 0;
  while Node2 <> nil do begin
    if Node2^.Next <> Node1 then
      raise Exception.Create(Format('CheckLinks: Node[%d].Next <> next node', [-I]));
    Node1 := Node2;
    Node2 := Node2^.Prev;
    Inc(I);
  end;
  if I <> List.Count then
    raise Exception.Create(Format('CheckLinks: b) .Count = %d but %d node(s)', [List.Count, I]));
end;

procedure TheListTest.Done(Node: TNodeP);
begin
  Dispose(Node);
end;

procedure TheListTest.SetUp;
begin
  List := TList_.Create;
end;

procedure TheListTest.TearDown;
begin
  try
    CheckLinks;
  finally
    FreeAndNil(List);
  end;
end;

procedure TheListTest.TestCreate;
begin
  AssertEquals('Initial .Count', 0, List.Count);
  AssertSame('.First', nil, List.First);
  AssertSame('.Last', nil, List.Last);
  CheckLinks;
end;

procedure TheListTest.TestClear;
const N = 10;
var I: Integer;
begin
  for I := 0 to N - 1 do
    List.PushBack(Item(I));
  List.Clear;
  CheckLinks;
  AssertEquals('.Count', 0, List.Count);
  AssertSame('.First', nil, List.First);
  AssertSame('.Last', nil, List.Last);
end;

procedure TheListTest.TestPushFront;
var Node1, Node2, Node3: TNodeP;
begin
  Node1 := List.PushFront(Item(1));
  CheckLinks;
  AssertSame('a)', Node1, List.First);
  AssertSame('b)', Node1, List.Last);
  AssertEquals('c)', 1, Value(List.First^.Item));
  Node2 := List.PushFront(Item(2));
  CheckLinks;
  AssertSame('d)', Node2, List.First);
  AssertSame('e)', Node1, List.Last);
  AssertEquals('f)', 2, Value(List.First^.Item));
  AssertEquals('g)', 1, Value(List.Last^.Item));
  Node3 := List.PushFront(Item(3));
  CheckLinks;
  AssertSame('h)', Node3, List.First);
  AssertSame('i)', Node1, List.Last);
  AssertEquals('j)', 3, Value(List.First^.Item));
  AssertEquals('k)', 1, Value(List.Last^.Item));
  Assert(Node1 = Node1); // hint off
  Assert(Node2 = Node2); // hint off
  Assert(Node3 = Node3); // hint off
end;

procedure TheListTest.TestPushBack;
var Node1, Node2, Node3: TNodeP;
begin
  Node1 := List.PushBack(Item(1));
  CheckLinks;
  AssertSame('a)', Node1, List.First);
  AssertSame('b)', Node1, List.Last);
  AssertEquals('c)', 1, Value(List.First^.Item));
  Node2 := List.PushBack(Item(2));
  CheckLinks;
  AssertSame('d)', Node1, List.First);
  AssertSame('e)', Node2, List.Last);
  AssertEquals('f)', 1, Value(List.First^.Item));
  AssertEquals('g)', 2, Value(List.Last^.Item));
  Node3 := List.PushBack(Item(3));
  CheckLinks;
  AssertSame('h)', Node1, List.First);
  AssertSame('i)', Node3, List.Last);
  AssertEquals('j)', 1, Value(List.First^.Item));
  AssertEquals('k)', 3, Value(List.Last^.Item));
  Assert(Node1 = Node1); // hint off
  Assert(Node2 = Node2); // hint off
  Assert(Node3 = Node3); // hint off
end;

procedure TheListTest.TestMoveToFront;
var Node1, Node2, Node3: TNodeP;
begin
  // 1 -> 1
  Node1 := List.PushBack(Item(1));
  AssertSame('a1)', Node1, List.First);
  AssertSame('b1)', Node1, List.Last);
  AssertSame('c1)', Node1, List.MoveToFront(Node1));
  CheckLinks;
  AssertSame('d1)', Node1, List.First);
  AssertSame('e1)', Node1, List.Last);
  TearDown;

  // 1 2 -> 1 2
  Setup;
  Node1 := List.PushBack(Item(1));
  Node2 := List.PushBack(Item(2));
  AssertSame('a2)', Node1, List.First);
  AssertSame('b2)', Node2, List.Last);
  AssertSame('c2)', Node1, List.MoveToFront(Node1));
  CheckLinks;
  AssertSame('d2)', Node1, List.First);
  AssertSame('e2)', Node2, List.Last);
  TearDown;

  // 1 2 -> 2 1
  Setup;
  Node1 := List.PushBack(Item(1));
  Node2 := List.PushBack(Item(2));
  AssertSame('a3)', Node1, List.First);
  AssertSame('b3)', Node2, List.Last);
  AssertSame('c3)', Node2, List.MoveToFront(Node2));
  CheckLinks;
  AssertSame('d3)', Node2, List.First);
  AssertSame('e3)', Node1, List.Last);
  TearDown;

  // 1 2 3 -> 1 2 3
  Setup;
  Node1 := List.PushBack(Item(1));
  Node2 := List.PushBack(Item(2));
  Node3 := List.PushBack(Item(3));
  AssertSame('a4)', Node1, List.First);
  AssertSame('b4)', Node3, List.Last);
  AssertSame('c4)', Node1, List.MoveToFront(Node1));
  CheckLinks;
  AssertSame('d4)', Node1, List.First);
  AssertSame('e4)', Node3, List.Last);
  TearDown;

  // 1 2 3 -> 2 1 3
  Setup;
  Node1 := List.PushBack(Item(1));
  Node2 := List.PushBack(Item(2));
  Node3 := List.PushBack(Item(3));
  AssertSame('a5)', Node1, List.First);
  AssertSame('b5)', Node3, List.Last);
  AssertSame('c5)', Node2, List.MoveToFront(Node2));
  CheckLinks;
  AssertSame('d5)', Node2, List.First);
  AssertSame('e5)', Node3, List.Last);
  TearDown;

  // 1 2 3 -> 3 1 2
  Setup;
  Node1 := List.PushBack(Item(1));
  Node2 := List.PushBack(Item(2));
  Node3 := List.PushBack(Item(3));
  AssertSame('a6)', Node1, List.First);
  AssertSame('b6)', Node3, List.Last);
  AssertSame('c6)', Node3, List.MoveToFront(Node3));
  CheckLinks;
  AssertSame('d6)', Node3, List.First);
  AssertSame('e6)', Node2, List.Last);
  Assert(Node1 = Node1); // hint off
  Assert(Node2 = Node2); // hint off
  Assert(Node3 = Node3); // hint off
end;

procedure TheListTest.TestMoveToBack;
var Node1, Node2, Node3: TNodeP;
begin
  // 1 -> 1
  Node1 := List.PushBack(Item(1));
  AssertSame('a1)', Node1, List.First);
  AssertSame('b1)', Node1, List.Last);
  AssertSame('c1)', Node1, List.MoveToBack(Node1));
  CheckLinks;
  AssertSame('d1)', Node1, List.First);
  AssertSame('e1)', Node1, List.Last);
  TearDown;

  // 1 2 -> 1 2
  Setup;
  Node1 := List.PushBack(Item(1));
  Node2 := List.PushBack(Item(2));
  AssertSame('a2)', Node1, List.First);
  AssertSame('b2)', Node2, List.Last);
  AssertSame('c2)', Node2, List.MoveToBack(Node2));
  CheckLinks;
  AssertSame('d2)', Node1, List.First);
  AssertSame('e2)', Node2, List.Last);
  TearDown;

  // 1 2 -> 2 1
  Setup;
  Node1 := List.PushBack(Item(1));
  Node2 := List.PushBack(Item(2));
  AssertSame('a3)', Node1, List.First);
  AssertSame('b3)', Node2, List.Last);
  AssertSame('c3)', Node1, List.MoveToBack(Node1));
  CheckLinks;
  AssertSame('d3)', Node2, List.First);
  AssertSame('e3)', Node1, List.Last);
  TearDown;

  // 1 2 3 -> 1 2 3
  Setup;
  Node1 := List.PushBack(Item(1));
  Node2 := List.PushBack(Item(2));
  Node3 := List.PushBack(Item(3));
  AssertSame('a4)', Node1, List.First);
  AssertSame('b4)', Node3, List.Last);
  AssertSame('c4)', Node3, List.MoveToBack(Node3));
  CheckLinks;
  AssertSame('d4)', Node1, List.First);
  AssertSame('e3)', Node3, List.Last);
  TearDown;

  // 1 2 3 -> 1 3 2
  Setup;
  Node1 := List.PushBack(Item(1));
  Node2 := List.PushBack(Item(2));
  Node3 := List.PushBack(Item(3));
  AssertSame('a5)', Node1, List.First);
  AssertSame('b5)', Node3, List.Last);
  AssertSame('c5)', Node2, List.MoveToBack(Node2));
  CheckLinks;
  AssertSame('d5)', Node1, List.First);
  AssertSame('e5)', Node2, List.Last);
  TearDown;

  // 1 2 3 -> 2 3 1
  Setup;
  Node1 := List.PushBack(Item(1));
  Node2 := List.PushBack(Item(2));
  Node3 := List.PushBack(Item(3));
  AssertSame('a6)', Node1, List.First);
  AssertSame('b6)', Node3, List.Last);
  AssertSame('c6)', Node1, List.MoveToBack(Node1));
  CheckLinks;
  AssertSame('d6)', Node2, List.First);
  AssertSame('e6)', Node1, List.Last);
  Assert(Node1 = Node1); // hint off
  Assert(Node2 = Node2); // hint off
  Assert(Node3 = Node3); // hint off
end;

procedure TheListTest.TestInsertAfter;
var Node1, Node2, Node3: TNodeP;
begin
  // 1 -> 1 2
  Node1 := List.PushBack(Item(1));
  Node2 := List.InsertAfter(Node1, Item(2));
  CheckLinks;
  AssertSame('a1)', Node1, List.First);
  AssertSame('b1)', Node2, List.Last);
  TearDown;

  // 1 2 -> 1 3 2
  SetUp;
  Node1 := List.PushBack(Item(1));
  Node2 := List.PushBack(Item(2));
  Node3 := List.InsertAfter(Node1, Item(3));
  CheckLinks;
  AssertSame('a2)', Node1, List.First);
  AssertSame('b2)', Node2, List.Last);
  TearDown;

  // 1 2 -> 1 2 3
  SetUp;
  Node1 := List.PushBack(Item(1));
  Node2 := List.PushBack(Item(2));
  Node3 := List.InsertAfter(Node2, Item(3));
  CheckLinks;
  AssertSame('a3)', Node1, List.First);
  AssertSame('b3)', Node3, List.Last);
  Assert(Node1 = Node1); // hint off
  Assert(Node2 = Node2); // hint off
  Assert(Node3 = Node3); // hint off
end;

procedure TheListTest.TestInsertBefore;
var Node1, Node2, Node3: TNodeP;
begin
  // 1 -> 2 1
  Node1 := List.PushBack(Item(1));
  Node2 := List.InsertBefore(Item(2), Node1);
  CheckLinks;
  AssertSame('a1)', Node2, List.First);
  AssertSame('b1)', Node1, List.Last);
  TearDown;

  // 1 2 -> 3 1 2
  SetUp;
  Node1 := List.PushBack(Item(1));
  Node2 := List.PushBack(Item(2));
  Node3 := List.InsertBefore(Item(3), Node1);
  CheckLinks;
  AssertSame('a2)', Node3, List.First);
  AssertSame('b2)', Node2, List.Last);
  TearDown;

  // 1 2 -> 1 3 2
  SetUp;
  Node1 := List.PushBack(Item(1));
  Node2 := List.PushBack(Item(2));
  Node3 := List.InsertBefore(Item(3), Node2);
  CheckLinks;
  AssertSame('a3)', Node1, List.First);
  AssertSame('b3)', Node2, List.Last);
  Assert(Node1 = Node1); // hint off
  Assert(Node2 = Node2); // hint off
  Assert(Node3 = Node3); // hint off
end;

procedure TheListTest.TestMoveAfter;
var Node1, Node2, Node3: TNodeP;
begin
  // 1 2 -> 2 1
  Node1 := List.PushBack(Item(1));
  Node2 := List.PushBack(Item(2));
  AssertSame('a1)', Node1, List.MoveAfter(Node2, Node1));
  CheckLinks;
  AssertSame('b1)', Node2, List.First);
  AssertSame('c1)', Node1, List.Last);
  TearDown;

  // 1 2 -> 1 2
  SetUp;
  Node1 := List.PushBack(Item(1));
  Node2 := List.PushBack(Item(2));
  AssertSame('a2)', Node2, List.MoveAfter(Node1, Node2));
  CheckLinks;
  AssertSame('b2)', Node1, List.First);
  AssertSame('c2)', Node2, List.Last);
  TearDown;

  // 1 2 3 -> 2 1 3
  SetUp;
  Node1 := List.PushBack(Item(1));
  Node2 := List.PushBack(Item(2));
  Node3 := List.PushBack(Item(3));
  AssertSame('a3)', Node1, List.MoveAfter(Node2, Node1));
  CheckLinks;
  AssertSame('b3)', Node2, List.First);
  AssertSame('c3)', Node3, List.Last);
  TearDown;

  // 1 2 3 -> 2 3 1
  SetUp;
  Node1 := List.PushBack(Item(1));
  Node2 := List.PushBack(Item(2));
  Node3 := List.PushBack(Item(3));
  AssertSame('a4)', Node1, List.MoveAfter(Node3, Node1));
  CheckLinks;
  AssertSame('b4)', Node2, List.First);
  AssertSame('c4)', Node1, List.Last);
  TearDown;

  // 1 2 3 -> 1 2 3
  SetUp;
  Node1 := List.PushBack(Item(1));
  Node2 := List.PushBack(Item(2));
  Node3 := List.PushBack(Item(3));
  AssertSame('a5)', Node2, List.MoveAfter(Node1, Node2));
  CheckLinks;
  AssertSame('b5)', Node1, List.First);
  AssertSame('c5)', Node3, List.Last);
  TearDown;

  // 1 2 3 -> 1 3 2
  SetUp;
  Node1 := List.PushBack(Item(1));
  Node2 := List.PushBack(Item(2));
  Node3 := List.PushBack(Item(3));
  AssertSame('a6)', Node2, List.MoveAfter(Node3, Node2));
  CheckLinks;
  AssertSame('b6)', Node1, List.First);
  AssertSame('c6)', Node2, List.Last);
  TearDown;

  // 1 2 3 -> 1 3 2
  SetUp;
  Node1 := List.PushBack(Item(1));
  Node2 := List.PushBack(Item(2));
  Node3 := List.PushBack(Item(3));
  AssertSame('a7)', Node3, List.MoveAfter(Node1, Node3));
  CheckLinks;
  AssertSame('b7)', Node1, List.First);
  AssertSame('c7)', Node2, List.Last);
  TearDown;

  // 1 2 3 -> 1 2 3
  SetUp;
  Node1 := List.PushBack(Item(1));
  Node2 := List.PushBack(Item(2));
  Node3 := List.PushBack(Item(3));
  AssertSame('a8)', Node3, List.MoveAfter(Node2, Node3));
  CheckLinks;
  AssertSame('b8)', Node1, List.First);
  AssertSame('c8)', Node3, List.Last);
  Assert(Node1 = Node1); // hint off
  Assert(Node2 = Node2); // hint off
  Assert(Node3 = Node3); // hint off
end;

procedure TheListTest.TestMoveBefore;
var Node1, Node2, Node3: TNodeP;
begin
  // 1 2 -> 1 2
  Node1 := List.PushBack(Item(1));
  Node2 := List.PushBack(Item(2));
  AssertSame('a1)', Node1, List.MoveBefore(Node1, Node2));
  CheckLinks;
  AssertSame('b1)', Node1, List.First);
  AssertSame('c1)', Node2, List.Last);
  TearDown;

  // 1 2 -> 2 1
  Setup;
  Node1 := List.PushBack(Item(1));
  Node2 := List.PushBack(Item(2));
  AssertSame('a2)', Node2, List.MoveBefore(Node2, Node1));
  CheckLinks;
  AssertSame('b2)', Node2, List.First);
  AssertSame('c2)', Node1, List.Last);
  TearDown;

  // 1 2 3 -> 1 2 3
  Setup;
  Node1 := List.PushBack(Item(1));
  Node2 := List.PushBack(Item(2));
  Node3 := List.PushBack(Item(3));
  AssertSame('a3)', Node1, List.MoveBefore(Node1, Node2));
  CheckLinks;
  AssertSame('b3)', Node1, List.First);
  AssertSame('c3)', Node3, List.Last);
  TearDown;

  // 1 2 3 -> 2 1 3
  Setup;
  Node1 := List.PushBack(Item(1));
  Node2 := List.PushBack(Item(2));
  Node3 := List.PushBack(Item(3));
  AssertSame('a4)', Node1, List.MoveBefore(Node1, Node3));
  CheckLinks;
  AssertSame('b4)', Node2, List.First);
  AssertSame('c4)', Node3, List.Last);
  TearDown;

  // 1 2 3 -> 2 1 3
  Setup;
  Node1 := List.PushBack(Item(1));
  Node2 := List.PushBack(Item(2));
  Node3 := List.PushBack(Item(3));
  AssertSame('a5)', Node2, List.MoveBefore(Node2, Node1));
  CheckLinks;
  AssertSame('b5)', Node2, List.First);
  AssertSame('c5)', Node3, List.Last);
  TearDown;

  // 1 2 3 -> 1 2 3
  Setup;
  Node1 := List.PushBack(Item(1));
  Node2 := List.PushBack(Item(2));
  Node3 := List.PushBack(Item(3));
  AssertSame('a6)', Node2, List.MoveBefore(Node2, Node3));
  CheckLinks;
  AssertSame('b6)', Node1, List.First);
  AssertSame('c6)', Node3, List.Last);
  TearDown;

  // 1 2 3 -> 3 1 2
  Setup;
  Node1 := List.PushBack(Item(1));
  Node2 := List.PushBack(Item(2));
  Node3 := List.PushBack(Item(3));
  AssertSame('a7)', Node3, List.MoveBefore(Node3, Node1));
  CheckLinks;
  AssertSame('b7)', Node3, List.First);
  AssertSame('c7)', Node2, List.Last);
  TearDown;

  // 1 2 3 -> 1 3 2
  Setup;
  Node1 := List.PushBack(Item(1));
  Node2 := List.PushBack(Item(2));
  Node3 := List.PushBack(Item(3));
  AssertSame('a8)', Node3, List.MoveBefore(Node3, Node2));
  CheckLinks;
  AssertSame('b8)', Node1, List.First);
  AssertSame('c8)', Node2, List.Last);
  Assert(Node1 = Node1); // hint off
  Assert(Node2 = Node2); // hint off
  Assert(Node3 = Node3); // hint off
end;

procedure TheListTest.TestExtract;
var Node1, Node2, Node3: TNodeP;
begin
  // 1 ->
  Node1 := List.PushBack(Item(1));
  AssertSame('a1)', Node1, List.Extract(Node1));
  Done(Node1);
  CheckLinks;
  AssertEquals('b1)', 0, List.Count);
  TearDown;

  // 1 2 -> 2
  SetUp;
  Node1 := List.PushBack(Item(1));
  Node2 := List.PushBack(Item(2));
  AssertSame('a2)', Node1, List.Extract(Node1));
  Done(Node1);
  CheckLinks;
  AssertEquals('b2)', 1, List.Count);
  AssertSame('c2)', Node2, List.First);
  AssertSame('d2)', Node2, List.Last);
  TearDown;

  // 1 2 -> 1
  SetUp;
  Node1 := List.PushBack(Item(1));
  Node2 := List.PushBack(Item(2));
  AssertSame('a3)', Node2, List.Extract(Node2));
  Done(Node2);
  CheckLinks;
  AssertEquals(1, List.Count);
  AssertSame('b3)', Node1, List.First);
  AssertSame('c3)', Node1, List.Last);
  TearDown;

  // 1 2 3 -> 2 3
  SetUp;
  Node1 := List.PushBack(Item(1));
  Node2 := List.PushBack(Item(2));
  Node3 := List.PushBack(Item(3));
  AssertSame('a4)', Node1, List.Extract(Node1));
  Done(Node1);
  CheckLinks;
  AssertEquals(2, List.Count);
  AssertSame('b4)', Node2, List.First);
  AssertSame('c4)', Node3, List.Last);
  TearDown;

  // 1 2 3 -> 1 3
  SetUp;
  Node1 := List.PushBack(Item(1));
  Node2 := List.PushBack(Item(2));
  Node3 := List.PushBack(Item(3));
  AssertSame('a5)', Node2, List.Extract(Node2));
  Done(Node2);
  CheckLinks;
  AssertEquals(2, List.Count);
  AssertSame('b5)', Node1, List.First);
  AssertSame('c5)', Node3, List.Last);
  TearDown;

  // 1 2 3 -> 1 2
  SetUp;
  Node1 := List.PushBack(Item(1));
  Node2 := List.PushBack(Item(2));
  Node3 := List.PushBack(Item(3));
  AssertSame('a6)', Node3, List.Extract(Node3));
  Done(Node3);
  CheckLinks;
  AssertEquals(2, List.Count);
  AssertSame('b5)', Node1, List.First);
  AssertSame('c5)', Node2, List.Last);
end;

procedure TheListTest.TestRemove;
var Node1, Node2, Node3: TNodeP;
begin
  // 1 ->
  Node1 := List.PushBack(Item(1));
  List.Remove(Node1);
  CheckLinks;
  AssertEquals('a1)', 0, List.Count);
  TearDown;

  // 1 2 -> 2
  SetUp;
  Node1 := List.PushBack(Item(1));
  Node2 := List.PushBack(Item(2));
  List.Remove(Node1);
  CheckLinks;
  AssertEquals('a2)', 1, List.Count);
  AssertSame('b2)', Node2, List.First);
  AssertSame('c2)', Node2, List.Last);
  TearDown;

  // 1 2 -> 1
  SetUp;
  Node1 := List.PushBack(Item(1));
  Node2 := List.PushBack(Item(2));
  List.Remove(Node2);
  CheckLinks;
  AssertEquals('a3)', 1, List.Count);
  AssertSame('b3)', Node1, List.First);
  AssertSame('c3)', Node1, List.Last);
  TearDown;

  // 1 2 3 -> 2 3
  SetUp;
  Node1 := List.PushBack(Item(1));
  Node2 := List.PushBack(Item(2));
  Node3 := List.PushBack(Item(3));
  List.Remove(Node1);
  CheckLinks;
  AssertEquals('a4)', 2, List.Count);
  AssertSame('b4)', Node2, List.First);
  AssertSame('c4)', Node3, List.Last);
  TearDown;

  // 1 2 3 -> 1 3
  SetUp;
  Node1 := List.PushBack(Item(1));
  Node2 := List.PushBack(Item(2));
  Node3 := List.PushBack(Item(3));
  List.Remove(Node2);
  CheckLinks;
  AssertEquals('a5)', 2, List.Count);
  AssertSame('b5)', Node1, List.First);
  AssertSame('c5)', Node3, List.Last);
  TearDown;

  // 1 2 3 -> 1 2
  SetUp;
  Node1 := List.PushBack(Item(1));
  Node2 := List.PushBack(Item(2));
  Node3 := List.PushBack(Item(3));
  List.Remove(Node3);
  CheckLinks;
  AssertEquals('a6)', 2, List.Count);
  AssertSame('b6)', Node1, List.First);
  AssertSame('c6)', Node2, List.Last);
  Assert(Node1 = Node1); // hint off
  Assert(Node2 = Node2); // hint off
  Assert(Node3 = Node3); // hint off
end;

initialization
  RegisterTests([
    TheIntListTest,
    TheStrListTest,
    TheInterfaceListTest,
    TheObjectListTest
  ]);

end.

